Low-Density Parity-Check (LDPC) codes were introduced by Gallager in 1962 and rediscovered in 1996 by MacKay and Neal. LDPC codes are also described for example in U.S. Publication 2003/0126551. For a long time they had no practical impact due to their computational and implementation complexity. This changed with advances in microelectronics that led to more computational power at hand for simulation and which now enables implementation. Due to their excellent error correction performance they are considered for future telecommunication standards.
An LDPC code is a linear block code defined by its sparse×N parity check matrix H. It contains j ones per column and k ones per row, called row and column degree respectively. A (j,k)-regular LDPC code has row and column degree of uniform weight, otherwise the code is called irregular. A parity check code can be represented by a bipartite graph. The M check nodes correspond to the parity constraints, the N variable nodes represent the data symbols of the codeword. An edge in the graph corresponds to a one in the parity check matrix.
In the LDPC code encoder the packet to encode of size (N−M) is multiplied with a generator matrix G of size (N−M)×N. This multiplication leads to an encoded vector of length N. The generator matrix G and the parity check matrix H satisfy the relation GHt=0 where 0 is the null matrix. Generally, an LDPC code decoder comprises a decoding module which receives the encoded vector of length N and delivers an intermediate vector of length N by using the parity check H. Then a demapping module extracts from the intermediate vector the decoded vector of length (N−M).
More precisely, LDPC codes can be decoded using message passing processes or algorithms, either in hard or soft decision form. The decoding is then an iterative process, which exchanges messages between variable and check nodes. Typically a Belief Propagation (BP) algorithm is used, which exchanges soft-information iteratively between variable and check nodes. The code performance mainly depends on the randomness of the parity check matrix, the codeword size N and the code rate R=(N−M)/N.
Many publications describe LDPC decoders and the algorithm implemented therein. An example of such a publication is “VLSI Implementation-Oriented (3,k)-Regular Low-Density Check Codes”, Tong, IEEE Workshop on Signal Processing Systems (SiPs), September 2001.
The channel coding part is a very important component in wireless communication systems like UMTS, WLAN and WPAN. Especially in the domain of WLAN and WPAN the latency of the decoding is of a critical importance. Low Density Parity Check codes can be seen as a promising candidate for this kind of systems in the near future. These codes are being used in the future version of DVB-S and in some fiber optical communication systems. More applications will follow in the near future.
The codes have some very interesting properties, which make them a natural choice for latency critical application. In a typical wireless system the payload on the wireless channel is fixed by the modulation and the framing structure. To be able to use the wireless channel resources in the most efficient way the data stream needs to be adapted during the coding process to fit into the given constrains. A coding rate adaptation in the channel encoder does this. In existing systems, puncturing and repetition usually perform this adaptation.
U.S. Publication 2003/0126551 mentioned above proposes the LDPC codes for ARQ scheme, but in this publication a simple puncturing is used to generate the higher rate codes. The punctured bits are stored in the transmitter and only transmitted when needed. So, the complete codeword has to be generated each time leading to higher power consumption.